package com.example.demo.Calss16_graph;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: java_base
 * @description: 图结构的宽度优先遍历
 * @author: zhouhongtao
 * @happyCreateTime: 2022/03/02 09:12
 */
public class Code01_BFSDemo {

    // 对 图结构 宽度优先遍历
    // 使用一个队列，还需要一个标识类的结构，需要标记此节点是否遍历过，因为可能存在环形结构！
    // 从node出发，进行宽度优先遍历
    public static void bfs(Node start) {
        if (start == null) {
            return;
        }
        Queue<Node> queue = new LinkedList();
        HashSet set = new HashSet();
        queue.add(start);
        set.add(start);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.println(node.value);
            if (!node.nexts.isEmpty()) {
                for (Node inn : node.nexts) {
                    if (!set.contains(inn)){
                        queue.add(inn);
                        set.add(inn);
                    }
                }
            }
        }
    }
}
